#include<iostream>

using namespace std;

template< class T >
class Node{
public:
    T data;
    Node<T> *next;

    explicit Node ( const T &_in ) : data( _in ), next(NULL){;}
    Node ( const Node &_n )
    {
        data = _n.data;
        next = _n.next;
    }
    
    ~Node ( void ){ ; }
    
    friend ostream & operator << ( ostream &out, const Node<T> &node )
    {
        out << "data: " << node.data <<" ,nextPtr: " << node.next;
    }
};

template< class T >
class Stack{
private:
    Node<T> *head;
    long size;
    
public:
    Stack() : head(NULL), size(0) {;}
    ~Stack(){ ; }
    
    const long & getSize() const { return size; }
    
    void push( const T &_in )
    {
        Node<T> *node = new Node<T>( _in );
        node->next = head;
        head = node;
        size++;
    }
    
    void traverse()const
    {
        Node<T> *next = head;
        
        while( next )
        {
            cout << ">> " << next->data << endl;
            next = next->next;
        }
    }
    
    const T popData()
    { 
        return pop().data; 
    }
    
    const Node<T> pop()
    {
        // check if empty
        if ( !head )
        {
            cout << "pop EMPTY stack" << endl;
            throw -1;
        }
            
        Node<T> top = *head;
        Node<T> *del = head;
        head = head->next;
        delete del;
        size--;
        return top;
    }
    
    void clean()
    {
        while( head )
        {   
            Node<T> *del = head; // store pointer for deletion
            head = head->next;   // update head's next
            delete del;
        }
        head = NULL;
        size = 0;
    }    
};


int main()
{
    Stack<int> stack;
    int sz = 100;
    for(int i=0; i<sz; i++)
    {
        stack.push(i);
        cout << "push @ " << i <<" : " << stack.getSize() << endl;
    }
    cout << "stack size: " << stack.getSize() << endl;
    
    stack.traverse();
    
    /*
    cout << "execute clean" << endl;
    stack.clean();
    cout << "after clean: " << stack.getSize() << endl;
    exit(0);
    */
    
    int ss = stack.getSize();
    cout <<"test pop, stack size: " << ss << endl;
    for(int i=0; i<ss; i++)
    {
        cout <<"pop: " << stack.popData() << " ,stack size: ";
        cout << stack.getSize() << endl;
    }    
    cout << "stack size: " << stack.getSize() << endl;
}